﻿/* Copyright (c) 2011 Mahir Iqbal
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

package com.bayvakoof.dewall
{
	import com.bayvakoof.dewall.geom.Axis;
	import com.bayvakoof.dewall.geom.Face;
	import com.bayvakoof.dewall.geom.Triangle;
	
	import flash.geom.Point;
	import flash.geom.Rectangle;
	
	/**
	 * ...
	 * @author Mahir Iqbal
	 */
	public class DelaunayTriangulator
	{
		const FAST_MINIMUM:int = 1010; // Amount of points needed to switch from makeTriangle to makeTriangleFast
		
		private var triangles:Vector.<Triangle>;
		
		private var faces:Vector.<Face>;
		
		public function DelaunayTriangulator()
		{
			// Do nothing
		}
		
		public function generate(points:Vector.<Point>, constrainedEdges:Vector.<Point> = null):Vector.<Triangle>
		{
			if (points.length < 3)
				throw Error("Not enough points to triangulate");
			
			triangles = new Vector.<Triangle>();
			faces = new Vector.<Face>();
			delaunayWall(new PointSet(points), new Vector.<Face>(), Axis.VERTICAL);
			if(constrainedEdges != null && constrainedEdges.length > 0 && constrainedEdges.length % 2 == 0)
			{
				for(var i: int = 0; i < constrainedEdges.length; i+=2)
				{
					var p1: Point = constrainedEdges[i];
					var p2: Point = constrainedEdges[i+1];
					var f: Face = findFace(p1, p2);
					if(f == null)
					{
						var removedTriangles:Vector.<Triangle> = new Vector.<Triangle>();
						var removedFaces:Vector.<Face> = new Vector.<Face>();
						var topPath:Vector.<Face> = new Vector.<Face>();
						var bottomPath:Vector.<Face> = new Vector.<Face>();
						//find triangle at p1 that intersect with p1, p2
						for(var j: int = triangles.length - 1; j >= 0; j--)
						{
							var tri:Triangle = triangles[j];
							if(tri.v1 == p1 || tri.v2 == p1 || tri.v3 == p1)
							{
								var currentFace: Face = tri.getOppositedFace(p1);
								if(testIntersection(p1.x, p1.y, p2.x, p2.y, currentFace.p1.x, currentFace.p1.y, currentFace.p2.x, currentFace.p2.y) == true)
								{
									var adjacentFaces:Array = tri.getAdjacentFaces(p1);
									topPath.push(adjacentFaces[0]);
									bottomPath.push(adjacentFaces[1]);
									removedTriangles.push(tri);
									
									var prevTri:Triangle = tri;
									do
									{
										var currentTri:Triangle = currentFace.getOppositedTriangle(prevTri);
										var oppositedPoint:Point = currentTri.getOppositedVertex(currentFace);
										
										removedFaces.push(currentFace);
										removedTriangles.push(currentTri);
										
										adjacentFaces = currentTri.getAdjacentFaces(oppositedPoint);
										var lastFace:Face = topPath[topPath.length-1];
										var addedFace:Face;
										if(oppositedPoint == p2)
										{
											addedFace = adjacentFaces[0];
											if(addedFace.p1 == lastFace.p1 || addedFace.p1 == lastFace.p2 || addedFace.p2 == lastFace.p1 || addedFace.p2 == lastFace.p2)
											{
												topPath.push(addedFace);
												bottomPath.push(adjacentFaces[1]);
											}
											else
											{
												topPath.push(adjacentFaces[1]);
												bottomPath.push(adjacentFaces[0]);
											}
										}
										else
										{
											currentFace = adjacentFaces[0];
											var addedFace:Face = adjacentFaces[1];
											if(testIntersection(p1.x, p1.y, p2.x, p2.y, currentFace.p1.x, currentFace.p1.y, currentFace.p2.x, currentFace.p2.y)==false)
											{
												currentFace = adjacentFaces[1];
												addedFace = adjacentFaces[0];
											}
											
											if(addedFace.p1 == lastFace.p1 || addedFace.p1 == lastFace.p2 || addedFace.p2 == lastFace.p1 || addedFace.p2 == lastFace.p2)
											{
												topPath.push(addedFace);
											}
											else
											{
												bottomPath.push(addedFace);
											}
										}
										
										prevTri = currentTri;
									} while(oppositedPoint != p2);
									break;
								}
							}
						}
						//delete triangles and face
						for each(var deletedTri:Triangle in removedTriangles)
						{
							deletedTri.face1.deleteTriangle(deletedTri);
							deletedTri.face2.deleteTriangle(deletedTri);
							deletedTri.face3.deleteTriangle(deletedTri);
							
							var idx:int = triangles.indexOf(deletedTri);
							triangles.splice(idx, 1);
						}
						for each(var face:Face in removedFaces)
						{
							var idx:int = faces.indexOf(face);
							faces.splice(idx, 1);
						}
						//triangulate two polygon
						if(topPath.length > 0 && bottomPath.length > 0)
						{
							var newFace:Face = createFace(p1, p2);// new Face(p1, p2);
							triangulatePolygon(newFace, topPath);
							triangulatePolygon(newFace, bottomPath);
						}
						
						for each(var fa:Face in faces)
						{
							if(fa.tri1 == null && fa.tri2 == null)
							{
								trace('');
							}
							if(fa.tri1 != null && triangles.indexOf(fa.tri1) < 0)
							{
								trace('');
							}
							if(fa.tri2 != null && triangles.indexOf(fa.tri2) < 0)
							{
								trace('');
							}
						}
					}
				}
			}
			return triangles;
		}
		
		private function delaunayWall(pointSet:PointSet, AFL:Vector.<Face>, splitDir:int, precomputedBounds:Rectangle = null): void
		{
			//var triangulation:Vector.<Triangle> = new Vector.<Triangle>();
			var points:Vector.<Point> = pointSet.points;
			
			var alpha:Axis;
			var size:int = points.length;
			var halfSize:int = (int) (size / 2);
			
			var axe:String;
			if (splitDir == Axis.VERTICAL)
			{
				points.sort(compareX);
				axe = 'x';
			} else
			{
				points.sort(compareY);
				axe = 'y';
			}
			
			var i:int = halfSize;
			var idx:int = i;
			var n:int = 0;
			var found:Boolean = false;
			while(n < halfSize && alpha == null)
			{
				if(i - n - 1 >= 0)
				{
					if(points[i - n][axe] != points[i - n - 1][axe])
					{
						alpha = new Axis(0.5 * (points[i - n][axe] + points[i - n - 1][axe]), splitDir);
						idx = i - n;
					}
					else if(i + n + 1 < points.length)
					{
						if(points[i + n][axe] != points[i + n + 1][axe])
						{
							alpha = new Axis(0.5 * (points[i + n][axe] + points[i + n + 1][axe]), splitDir);
							idx = i + n + 1;
						}
					}
				}
				n += 1;
			}
			
			if(alpha == null)
			{
				splitDir = (splitDir == Axis.VERTICAL) ? Axis.HORIZONTAL : Axis.VERTICAL;
				delaunayWall(pointSet, AFL, splitDir, precomputedBounds);
			}
			else
			{
				// Partition the points by the axis (the axis was created by sorting the points first).
				var partition1:Vector.<Point> = points.slice(0, idx);
				var partition2:Vector.<Point> = points.slice(idx, size);
				
				var precomputed1:Rectangle;
				var precomputed2:Rectangle;
				if (points.length > FAST_MINIMUM)
				{
					if (precomputedBounds)
						pointSet.createUG(precomputedBounds);
					else
						pointSet.createUG();
					
					if (points.length > 2 * FAST_MINIMUM)
					{
						if (splitDir == Axis.VERTICAL)
						{
							precomputed1 = new Rectangle(pointSet.bounds.left, pointSet.bounds.top, partition1[partition1.length - 1].x - pointSet.bounds.left, pointSet.bounds.height);
							precomputed2 = new Rectangle(partition2[0].x, pointSet.bounds.top, pointSet.bounds.right - partition2[0].x, pointSet.bounds.height);
						} else
						{
							precomputed1 = new Rectangle(pointSet.bounds.left, pointSet.bounds.top, pointSet.bounds.width, partition1[partition1.length - 1].y - pointSet.bounds.top);
							precomputed2 = new Rectangle(pointSet.bounds.left, partition2[0].y, pointSet.bounds.width, pointSet.bounds.bottom - partition2[0].y);
						}
					}
				}
				
				/* The Active Face Lists (AFLs) hold faces which can still create triangles.
				 * These lists are partitioned according to which side of the splitting axis
				 * they are on.
				 */
				var AFLalpha:Vector.<Face> = new Vector.<Face>();
				var AFL1:Vector.<Face> = new Vector.<Face>();
				var AFL2:Vector.<Face> = new Vector.<Face>();
				
				// Check if there are faces in the AFL
				if (AFL.length == 0)
				{
					var firstTriangle:Triangle = makeFirstTriangle(points, alpha, partition1, partition2);
					//triangles.push(firstTriangle);
					//AFL = AFL.concat(firstTriangle.faces);
					AFL.push(firstTriangle.face1, firstTriangle.face2, firstTriangle.face3);
				}
				
				// Loop through the existing faces and add them to each subset (AFLalpha, AFL1, AFL2)
				for each (var f:Face in AFL)
				{
					var p1Side:int = alpha.getSide(f.p1);
					if (p1Side == Face.ABOVE)
					{
						if (alpha.getSide(f.p2) == Face.ABOVE)
							AFL1.push(f);
						else
							AFLalpha.push(f);
					} else
					{
						if (alpha.getSide(f.p2) == Face.BELOW)
							AFL2.push(f);
						else
							AFLalpha.push(f);
					}
				}
				
				for each (var faceParse:Face in AFLalpha)
				{
					var t:Triangle;
					
					if (points.length > FAST_MINIMUM)
						t = makeTriangleFast(faceParse, pointSet);
					else
						t = makeTriangle(faceParse, points);
					
					if(t)
					{
						// Internally (from makeTriangle), I know that the new (i.e. nonFace) vertex is vertex3 of t.
						//var nonFacePoint:Point = t.vertices[2];
						/*var nonFacePoint:Point = t.v3;
						
						if (!faceParse.triPoint)
						{
							faceParse.triPoint = nonFacePoint;
						}*/
						
						// Add new faces to AFLs
						//var newFace1:Face = new Face(faceParse.p1, nonFacePoint);
						//newFace1.triPoint = faceParse.p2;
						var newFace1:Face = t.face1;
						
						//var newFace2:Face = new Face(faceParse.p2, nonFacePoint);
						//newFace2.triPoint = faceParse.p1;
						var newFace2:Face = t.face2;
						
						// Update the lists and triangulation progress for each incident point.
						if (alpha.getSide(newFace1.p1) == Face.ABOVE)
						{
							if (alpha.getSide(newFace1.p2) == Face.ABOVE)
								update(newFace1, AFL1);
							else
								update(newFace1, AFLalpha);
						} else
						{
							if (alpha.getSide(newFace1.p2) == Face.BELOW)
								update(newFace1, AFL2);
							else
								update(newFace1, AFLalpha);
						}
						
						if (alpha.getSide(newFace2.p1) == Face.ABOVE)
						{
							if (alpha.getSide(newFace2.p2) == Face.ABOVE)
								update(newFace2, AFL1);
							else
								update(newFace2, AFLalpha);
						} else
						{
							if (alpha.getSide(newFace2.p2) == Face.BELOW)
								update(newFace2, AFL2);
							else
								update(newFace2, AFLalpha);
						}
					}
				}
				
				splitDir = (splitDir == Axis.VERTICAL) ? Axis.HORIZONTAL : Axis.VERTICAL;
				
				if (AFL1.length != 0 && partition1.length > 1)
					delaunayWall(new PointSet(partition1), AFL1, splitDir, precomputed1);
					
				if (AFL2.length != 0 && partition2.length > 1)
					delaunayWall(new PointSet(partition2), AFL2, splitDir, precomputed2);
			}
		}
		
		private function update(face:Face, FL:Vector.<Face>):void
		{
			for (var i:int = 0; i < FL.length; i++)
			{
				//if (face.equals(FL[i]))
				if(face == FL[i])
				{
					FL.splice(i, 1);
					return;
				}
			}
			
			FL.push(face);
		}
		
		// Only called once per recursive triangulation (for 50 points, 500 points, etc.).
		private function makeFirstTriangle(points:Vector.<Point>, alpha:Axis, partition1:Vector.<Point>, partition2:Vector.<Point>)
		{
			var p:Point;
			
			// Points are still sorted at this point.
			var pointNearestToAxis:Point = partition2[0];
			
			var minDistance:Number = Number.POSITIVE_INFINITY;
			var distance:Number;
			// The point located across (i.e. in the other partition) from pointNearestToAxis that is closest to it.
			var oppositeClosestPoint:Point;
			for each (p in partition1)
			{
				distance = Point.distance(p, pointNearestToAxis); // TODO Use distance squared.
				if (distance < minDistance)
				{
					minDistance = distance;
					oppositeClosestPoint = p;
				}
			}
			
			// Construct a triangle with closestPoint and oppositeClosestPoint 
			// subject to the delaunay constraint.
			var minimumRadius:Number = Number.POSITIVE_INFINITY;
			var radius:Number;
			var delaunayPoint:Point;
			for each (p in points)
			{
				if(p != pointNearestToAxis && p != oppositeClosestPoint)
				{
					//var face:Face = new Face(pointNearestToAxis, oppositeClosestPoint);
					//var pSide:int = face.getSide(p);
					var pSide:int = getSide(pointNearestToAxis, oppositeClosestPoint, p);
					//var cc:Point = getCircumcenterLoc(face.p1, face.p2, p);
					var cc:Point = getCircumcenterLoc(pointNearestToAxis, oppositeClosestPoint, p);
					if(cc != null)
					{
						//var xDiff:Number = face.p1.x - cc.x;
						//var yDiff:Number = face.p1.y - cc.y;
						var xDiff:Number = pointNearestToAxis.x - cc.x;
						var yDiff:Number = pointNearestToAxis.y - cc.y;
						var radiusSquared:Number =  xDiff * xDiff + yDiff * yDiff;
						
						// Check if on the right side of the face.
						// Halfspace side is side of p
						//if (face.getSide(cc) != pSide)
						if(getSide(pointNearestToAxis, oppositeClosestPoint, cc) != pSide)
							radiusSquared *= -1;
						
						if (radiusSquared < minimumRadius)
						{
							delaunayPoint = p;
							minimumRadius = radiusSquared;
						}
					}
				}
			}
			
			var f1:Face = createFace(oppositeClosestPoint, delaunayPoint);// new Face(oppositeClosestPoint, delaunayPoint);
			var f2:Face = createFace(delaunayPoint, pointNearestToAxis);// new Face(delaunayPoint, pointNearestToAxis);
			var f3:Face = createFace(pointNearestToAxis, oppositeClosestPoint);// new Face(pointNearestToAxis, oppositeClosestPoint);
			
			faces.push(f1, f2, f3);
			var triangle:Triangle = createTriangle(pointNearestToAxis, oppositeClosestPoint, delaunayPoint, f1, f2, f3);
			triangles.push(triangle);
			return triangle;
		}
		
		private function makeTriangle(face:Face, points:Vector.<Point>):Triangle
		{
			var nonSearchSide;// = face.getSide(face.triPoint);
			nonSearchSide = face.tri1 != null ? face.triSide1 : face.triSide2;
			var delaunayPoint:Point;
			var minimumRadius:Number = Number.POSITIVE_INFINITY;
			
			for each (var p:Point in points)
			{
				var pSide:int = face.getSide(p);
				if (pSide != nonSearchSide)
				{
					var cc:Point = getCircumcenterLoc(face.p1, face.p2, p);
					if(cc != null)
					{
						var xDiff:Number = face.p1.x - cc.x;
						var yDiff:Number = face.p1.y - cc.y;
						var radiusSquared:Number =  xDiff * xDiff + yDiff * yDiff;
						
						// Check if on the right side of the face.
						// Halfspace side is side of p
						if (face.getSide(cc) != pSide)
							radiusSquared *= -1;
						
						if (radiusSquared < minimumRadius)
						{
							delaunayPoint = p;
							minimumRadius = radiusSquared;
						}
					}
				}
			}
			
			// If third vertex then found a new triangle, otherwise none			
			if (delaunayPoint)
			{
				//return new Triangle(face.p1, face.p2, delaunayPoint);
				return makeTriangle2(face, delaunayPoint);
			}
			
			return null;
		}		
			
		private const MAX_EXPANSIONS:int = 3;
		private function makeTriangleFast(face:Face, pointSet:PointSet):Triangle
		{
			/* Start searching points in grid cells in a specific order: 
			 * 		Create a circle, find grid cells that are in the circle AND that are also on the right side 
			 * 		 (halfSpace) of faceFace. (See Figure 6 on page 20 of DeWall paper.)
			 *
			 * 		i.e. "The search is then restricted to those cells contained in the circumsribed sphere
			 * 		with minimal radius." -http://www.kiv.zcu.cz/vyzkum/publikace/technicke-zpravy/2002/tr-2002-02.pdf
			 * 
			 * Illustrated algorithm in documentation.
			 */			
			var delaunayPoint:Point;
			var expansions:int = 0;
			
			var nonSearchSide;// = face.getSide(face.triPoint);
			nonSearchSide = face.tri1 != null ? face.triSide1 : face.triSide2;
			var centerX:Number, centerY:Number;	
			var midX:Number = (face.p1.x + face.p2.x) / 2;
			var midY:Number = (face.p1.y + face.p2.y) / 2;
			
			var faceRadius:Number = face.length * 0.5;
			var searchRadius:Number = 0;
			
			var padding:Number = pointSet.cellSize; // Pad the search boxes so no need to align them to the grid.
			
			var minimumRadius:Number = Number.POSITIVE_INFINITY;
			
			while (!delaunayPoint && expansions < MAX_EXPANSIONS)
			{
				searchRadius += faceRadius;
				
				// Get center of circle (see http://mathforum.org/library/drmath/view/53027.html if you don't want to think like me)
				var computationConstX:Number = Math.sqrt(Math.pow(searchRadius, 2) / face.lengthSquared - 0.25) * face.diffX;
				var computationConstY:Number = computationConstX * face.slope;
				if (nonSearchSide != Face.BELOW)
				{
					centerY = midY - computationConstX;
					centerX = midX + computationConstY;
				} else
				{
					centerY = midY + computationConstX;
					centerX = midX - computationConstY;
				}
			
				var boundingBox:Rectangle = new Rectangle(centerX - searchRadius, centerY - searchRadius, searchRadius * 2, searchRadius * 2);				
				
				for (var x:Number = Math.max(boundingBox.left, pointSet.gridBounds.left); x < Math.min(boundingBox.right + padding, pointSet.gridBounds.right); x += pointSet.cellSize)
				{
					for (var y:Number = Math.max(boundingBox.top, pointSet.gridBounds.top); y < Math.min(boundingBox.bottom + padding, pointSet.gridBounds.bottom); y += pointSet.cellSize)
					{
						var searchCell:Vector.<Point> = pointSet.uniformGrid[pointSet.hash(new Point(x, y))];
					
						if (searchCell)
						{
							for each (var p:Point in searchCell)
							{								
								var pSide:int = face.getSide(p);
								if (pSide != nonSearchSide)
								{
									var cc:Point = getCircumcenterLoc(face.p1, face.p2, p);
									var xDiff:Number = face.p1.x - cc.x;
									var yDiff:Number = face.p1.y - cc.y;
									var radiusSquared:Number =  xDiff * xDiff + yDiff * yDiff;
									
									// Check if on the right side of the face.
									// Halfspace side is side of p
									if (face.getSide(cc) != pSide)
										radiusSquared *= -1;
									
									if (radiusSquared < minimumRadius)
									{
										delaunayPoint = p;
										minimumRadius = radiusSquared;
									}
								}
							}
						}
					}
				}
				
				expansions++;
			}
			
			if (delaunayPoint)
			{				
				var currentRadius:Number = Math.sqrt(Math.abs(minimumRadius));
				
				if (currentRadius > searchRadius)
				{					
					searchRadius = currentRadius;
				
					// Get center of circle (see http://mathforum.org/library/drmath/view/53027.html if you don't want to think like me)
					var computationConstX:Number = Math.sqrt(Math.pow(searchRadius, 2) / face.lengthSquared - 0.25) * face.diffX;
					var computationConstY:Number = computationConstX * face.slope;
					if (nonSearchSide != Face.BELOW)
					{
						centerY = midY - computationConstX;
						centerX = midX + computationConstY;
					} else
					{
						centerY = midY + computationConstX;
						centerX = midX - computationConstY;
					}
				
					boundingBox = new Rectangle(centerX - searchRadius, centerY - searchRadius, searchRadius * 2, searchRadius * 2);				
					
					for (x = Math.max(boundingBox.left, pointSet.gridBounds.left); x < Math.min(boundingBox.right + padding, pointSet.gridBounds.right); x += pointSet.cellSize)
					{
						for (y = Math.max(boundingBox.top, pointSet.gridBounds.top); y < Math.min(boundingBox.bottom + padding, pointSet.gridBounds.bottom); y += pointSet.cellSize)
						{
							searchCell = pointSet.uniformGrid[pointSet.hash(new Point(x, y))];
						
							if (searchCell)
							{
								for each (var p:Point in searchCell)
								{									
									var pSide:int = face.getSide(p);
									if (pSide != nonSearchSide)
									{
										var cc:Point = getCircumcenterLoc(face.p1, face.p2, p);
										var xDiff:Number = face.p1.x - cc.x;
										var yDiff:Number = face.p1.y - cc.y;
										var radiusSquared:Number =  xDiff * xDiff + yDiff * yDiff;
										
										// Check if on the right side of the face.
										// Halfspace side is side of p
										if (face.getSide(cc) != pSide)
											radiusSquared *= -1;
										
										if (radiusSquared < minimumRadius)
										{
											delaunayPoint = p;
											minimumRadius = radiusSquared;
										}
									}
								}
							}
						}
					}
				}
			} else
			{				
				minimumRadius = Number.POSITIVE_INFINITY;
				for (x = pointSet.bounds.left; x < pointSet.gridBounds.right; x += pointSet.cellSize)
				{
					for (y = pointSet.bounds.top; y < pointSet.gridBounds.bottom; y += pointSet.cellSize)
					{
						searchCell = pointSet.uniformGrid[pointSet.hash(new Point(x, y))];
					
						if (searchCell)
						{						
							for each (var p:Point in searchCell)
							{
								var pSide:int = face.getSide(p);
								if (pSide != nonSearchSide)
								{
									var cc:Point = getCircumcenterLoc(face.p1, face.p2, p);
									var xDiff:Number = face.p1.x - cc.x;
									var yDiff:Number = face.p1.y - cc.y;
									var radiusSquared:Number =  xDiff * xDiff + yDiff * yDiff;
									
									// Check if on the right side of the face.
									// Halfspace side is side of p
									if (face.getSide(cc) != pSide)
										radiusSquared *= -1;
									
									if (radiusSquared < minimumRadius)
									{
										delaunayPoint = p;
										minimumRadius = radiusSquared;
									}
								}
							}
						}
					}
				}
			}
			
			if (delaunayPoint)
				//return new Triangle(face.p1, face.p2, delaunayPoint);
				return makeTriangle2(face, delaunayPoint);
				
			return null;
		}
		
		private function makeTriangle2(face:Face, delaunayPoint:Point): Triangle
		{
			var face1:Face = findFace(face.p2, delaunayPoint);
			if(face1 == null)
			{
				face1 = createFace(face.p2, delaunayPoint);// new Face(face.p2, delaunayPoint);
				faces.push(face1);
			}
			
			var face2:Face = findFace(delaunayPoint, face.p1);
			if(face2 == null)
			{
				face2 = createFace(delaunayPoint, face.p1);// new Face(delaunayPoint, face.p1);
				faces.push(face2);
			}
			
			/*var triangle:Triangle = new Triangle(face.p1, face.p2, delaunayPoint, face1, face2, face);
			triangles.push(triangle);
			if(face1.tri1 == null)
			{
				face1.tri1 = triangle;
				face1.triPoint1 = triangle.v1;
				face1.triSide1 = getSide(face1.p1, face1.p2, triangle.v1);
			}
			else
			{
				face1.tri2 = triangle;
				face1.triPoint2 = triangle.v1;
				face1.triSide2 = getSide(face1.p1, face1.p2, triangle.v1);
			}
			
			if(face2.tri1 == null)
			{
				face2.tri1 = triangle;
				face2.triPoint1 = triangle.v2;
				face2.triSide1 = getSide(face2.p1, face2.p2, triangle.v2);
			}
			else
			{
				face2.tri2 = triangle;
				face2.triPoint2 = triangle.v2;
				face2.triSide2 = getSide(face2.p1, face2.p2, triangle.v2);
			}
			
			if(face.tri1 == null)
			{
				face.tri1 = triangle;
				face.triPoint1 = triangle.v3;
				face.triSide1 = getSide(face.p1, face.p2, triangle.v3);
			}
			else
			{
				face.tri2 = triangle;
				face.triPoint2 = triangle.v3;
				face.triSide2 = getSide(face.p1, face.p2, triangle.v3);
			}*/
			var triangle:Triangle = createTriangle(face.p1, face.p2, delaunayPoint, face1, face2, face);
			triangles.push(triangle);
			//return new Triangle(face.p1, face.p2, delaunayPoint);
			return triangle;
		}
		
		private function createTriangle(p1:Point, p2:Point, p3:Point, face1:Face, face2:Face, face3:Face):Triangle
		{
			var triangle:Triangle = new Triangle(p1, p2, p3, face1, face2, face3);
			if(face1.tri1 == null)
			{
				face1.tri1 = triangle;
				face1.triPoint1 = triangle.v1;
				face1.triSide1 = getSide(face1.p1, face1.p2, triangle.v1);
			}
			else
			{
				face1.tri2 = triangle;
				face1.triPoint2 = triangle.v1;
				face1.triSide2 = getSide(face1.p1, face1.p2, triangle.v1);
			}
			
			if(face2.tri1 == null)
			{
				face2.tri1 = triangle;
				face2.triPoint1 = triangle.v2;
				face2.triSide1 = getSide(face2.p1, face2.p2, triangle.v2);
			}
			else
			{
				face2.tri2 = triangle;
				face2.triPoint2 = triangle.v2;
				face2.triSide2 = getSide(face2.p1, face2.p2, triangle.v2);
			}
			
			if(face3.tri1 == null)
			{
				face3.tri1 = triangle;
				face3.triPoint1 = triangle.v3;
				face3.triSide1 = getSide(face3.p1, face3.p2, triangle.v3);
			}
			else
			{
				face3.tri2 = triangle;
				face3.triPoint2 = triangle.v3;
				face3.triSide2 = getSide(face3.p1, face3.p2, triangle.v3);
			}
			
			return triangle;
		}
		
		private function createFace(p1:Point, p2:Point):Face
		{
			if (p2.x > p1.x)
			{
				return new Face(p2, p1);
			}
			return new Face(p1, p2);
		}
		
		private function compareX(p1:Point, p2:Point):Number
		{
			if (p1.x < p2.x)
				return -1;
			if (p1.x > p2.x)
				return 1;
			return 0;
		}
		
		private function compareY(p1:Point, p2:Point):Number
		{
			if (p1.y < p2.y)
				return -1;
			if (p1.y > p2.y)
				return 1;
			return 0;
		}
		
		private function calculateRadiusSquared(p1:Point, p2:Point, p3:Point):Number
		{
			var cc:Point = getCircumcenterLoc(p1, p2, p3);
			var xDiff:Number = p1.x - cc.x;
			var yDiff:Number = p1.y - cc.y;
			return xDiff * xDiff + yDiff * yDiff;
		}
		
		private function getCircumcenterLoc(p1:Point, p2:Point, p3:Point):Point
		{
			// Taken from John Shewchuk's posting on https://www.ics.uci.edu/~eppstein/junkyard/circumcenter.html			
			// 7 subtracts
			// 12 multiplies
			// 2 adds
			// 1 divide
			var xDiff21:Number = p2.x - p1.x;
			var yDiff21:Number = p2.y - p1.y;
			var xDiff31:Number = p3.x - p1.x;
			var yDiff31:Number = p3.y - p1.y;
			
			var length21:Number = xDiff21 * xDiff21 + yDiff21 * yDiff21;
			var length31:Number = xDiff31 * xDiff31 + yDiff31 * yDiff31;
			
			var denominator = 0.5 / (xDiff21 * yDiff31 - yDiff21 * xDiff31);
			if(denominator == Number.NEGATIVE_INFINITY || denominator == Number.POSITIVE_INFINITY)
			{
				return null;
			}
			return new Point(p1.x + (yDiff31 * length21 - yDiff21 * length31) * denominator, p1.y + (xDiff21 * length31 - xDiff31 * length21) * denominator);
		}
		
		private function triangulatePolygon(face:Face, path:Vector.<Face>):void
		{
			var p1:Point = face.p1;
			var p2:Point = face.p2;
			
			if(p1 != path[0].p1 && p1 != path[0].p2)
			{
				p1 = face.p2;
				p2 = face.p1;
			}
			
			if(path.length == 2)
			{
				//var p1:Point = face.p1;
				//var p2:Point = face.p2;
				var p3:Point;
				if(p1 == path[0].p1)
					p3 = path[0].p2;
				else
					p3 = path[0].p1;
				
				var face1:Face;
				var face2:Face;
				if(path[0].p1 != p1 && path[0].p2 != p1)
				{
					face1 = path[0];
					face2 = path[1];
				}
				else
				{
					face1 = path[1];
					face2 = path[0];
				}
				
				//var triangle:Triangle = new Triangle(p1, p2, p3, face1, face2, face);
				var triangle:Triangle = createTriangle(p1, p2, p3, face1, face2, face);
				triangles.push(triangle);
			}
			else
			{
				var ux:Number = p2.x - p1.x;
				var uy:Number = p2.y - p1.y;
				var a:Number = uy;
				var b:Number = -ux;
				var c:Number = -(uy * p1.x - ux * p1.y);
				
				var lowestPoint:Point;
				var minLength:Number = Number.MAX_VALUE;
				var lowestIndex:int = -1;
				var pt:Point = p1;
				for(var i: int = 0; i < path.length - 1; i++)
				{
					var f:Face = path[i];
					if(pt == f.p1)
						pt = f.p2;
					else
						pt = f.p1;
					var d:Number = Math.abs(a*pt.x + b*pt.y + c);
					if(d < minLength)
					{
						minLength = d;
						lowestIndex = i;
						lowestPoint = pt;
					}
				}
				
				var path1:Vector.<Face> = new Vector.<Face>();
				var path2:Vector.<Face> = new Vector.<Face>();
				for(var i: int = 0; i < path.length; i++)
				{
					if(i <= lowestIndex)
						path1.push(path[i]);
					else
						path2.push(path[i]);
				}
				
				var newFace:Face;
				if(path1.length == 1)
				{
					newFace = createFace(lowestPoint, p2);// new Face(lowestPoint, face.p2);
					path1.push(newFace);
					this.faces.push(newFace);
					
					triangulatePolygon(face, path1);
					triangulatePolygon(newFace, path2);
				}
				else if(path2.length == 1)
				{
					newFace = createFace(p1, lowestPoint);// new Face(face.p1, lowestPoint);
					path2.push(newFace);
					this.faces.push(newFace);
					
					triangulatePolygon(newFace, path1);
					triangulatePolygon(face, path2);
				}
				else
				{
					var path3:Vector.<Face> = new Vector.<Face>();
					newFace = createFace(p1, lowestPoint);// new Face(face.p1, lowestPoint);
					triangulatePolygon(newFace, path1);
					path3.push(newFace);
					this.faces.push(newFace);
					
					newFace = createFace(lowestPoint, p2);// new Face(lowestPoint, face.p2);
					triangulatePolygon(newFace, path2);
					path3.push(newFace);
					this.faces.push(newFace);
					
					triangulatePolygon(face, path3);
				}
			}
			
			/*var face1:Face = face;
			while(path.length > 0)
			{
				var face2:Face = path[0];
				var face3:Face;
				var p1:Point;
				var p2:Point;
				var p3:Point;
				if(face1.p1 == face2.p1 || face1.p1 == face2.p2)
				{
					p1 = face1.p1;
					p2 = face1.p2;
				}
				else
				{
					p1 = face1.p2;
					p2 = face1.p1;
				}
				if(face2.p1 == p1)
					p3 = face2.p2;
				else
					p3 = face2.p1;
				
				path.splice(0, 1);
				if(face1.p1 == path[0].p1 || face1.p1 == path[0].p2 || face1.p2 == path[0].p1 || face1.p2 == path[0].p2)
				{
					face3 = path[0];
					path.splice(0, 1);
				}
				else
				{
					face3 = new Face(p2, p3);
					faces.push(face3);
				}
				
				var triangle:Triangle = createTriangle(p1, p2, p3, face1, face2, face3);
				triangles.push(triangle);
				face1 = face3;
			}*/
		}
		
		private function findFace(p1:Point, p2:Point):Face
		{
			for each(var face:Face in faces)
			{
				if((face.p1 == p1 || face.p1 == p2) && (face.p2 == p1 || face.p2 == p2))
					return face;
			}
			return null;
		}
		
		private static const ABOVE:int = 1;  // In the case the slope of the line is infinite, this corresponds to LEFT
		private static const BELOW:int = -1; // whereas this is RIGHT
		private static const ON_LINE:int = 0;
		private function getSide(p1:Point, p2:Point, p:Point):int
		{
			// Need these values pretty often.
			/*var diffX:Number = p2.x - p1.x;
			var diffY:Number = p2.y - p1.y;
			var side:Number = diffX * (p.y - p1.y) - diffY * (p.x - p1.x);*/
			
			var diffX:Number;
			var diffY:Number
			var pStart:Point;
			if(p2.x > p1.x)
			{
				diffX = p1.x - p2.x;
				diffY = p1.y - p2.y;
				pStart = p2;
			}
			else
			{
				diffX = p2.x - p1.x;
				diffY = p2.y - p1.y;
				pStart = p1;
			}
			
			var side:Number = diffX * (p.y - pStart.y) - diffY * (p.x - pStart.x);
			
			if (side == 0)
				return 0;
			else
				return (side > 0) ? 1 : -1;
		}
		
		private var tolerance: Number = 0.0001;
		
		private function testIntersection(p1x: Number, p1y: Number, p2x: Number, p2y: Number, p3x: Number, p3y: Number, p4x: Number, p4y: Number): Boolean
		{
			var d1: Number;
			var d2: Number;
			var d3: Number;
			var d4: Number;
			
			d1 = crossproduct(p1x - p3x, p1y - p3y, p4x - p3x, p4y - p3y);
			d2 = crossproduct(p2x - p3x, p2y - p3y, p4x - p3x, p4y - p3y);
			d3 = crossproduct(p3x - p1x, p3y - p1y, p2x - p1x, p2y - p1y);
			d4 = crossproduct(p4x - p1x, p4y - p1y, p2x - p1x, p2y - p1y);
			
			//if(((d1 > tolerance && d2 < tolerance) || (d1 < tolerance && d2 > tolerance))
			//	&& ((d3 > tolerance && d4 < tolerance) || (d3 < tolerance && d4 > tolerance)))
			if(d1*d2 < 0 && d3*d4 < 0)
			{
				return true;
			}
			/*else if(d1 == 0 && onSegment(p3x, p3y, p4x, p4y, p1x, p1y))
			{
				return true;
			}
			else if(d2 == 0 && onSegment(p3x, p3y, p4x, p4y, p2x, p2y))
			{
				return true;
			}
			else if(d3 == 0 && onSegment(p1x, p1y, p2x, p2y, p3x, p3y))
			{
				return true;
			}
			else if(d4 == 0 && onSegment(p1x, p1y, p2x, p2y, p4x, p4y))
			{
				return true;
			}*/
			
			return false;
		}
		
		private function onSegment(p1x: Number, p1y: Number, p2x: Number, p2y: Number, px: Number, py: Number): Boolean
		{
			return Math.abs((px - p1x)*(p2y - p1y) - (py - p1y)*(p2x - p1x)) < tolerance;
		}
		
		private function crossproduct(v1x: Number, v1y: Number, v2x: Number, v2y: Number): Number
		{
			//Det(|x1	x2|
			//	  |y1	y2|)
			return v1x*v2y - v2x*v1y;
		}
	}
	
}